#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int xx[4] = { -1,0,1,0 }, yy[4] = { 0,1,0,-1 }, vis[105][105];
    int shortestBridge(vector<vector<int>>& a) {
        int n = a.size(), ans = n * n + 10, p = 1;
        vector<int> q1, q2;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (a[i][j] && vis[i][j] == 0) {
                    se(i, j, n, p, a);
                    p++;
                }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                if (vis[i][j] == 1) q1.push_back(i * n + j);
                else if (vis[i][j] == 2) q2.push_back(i * n + j);
            }
        for (int i = 0; i < q1.size(); i++)
            for (int j = 0; j < q2.size(); j++)
                ans = min(ans, cal(q1[i], q2[j], n));
        return ans;
    }
    void se(int x, int y, int n, int p, vector<vector<int>>& a) {
        vis[x][y] = p;
        for (int i = 0; i < 4; i++) {
            int nx = x + xx[i], ny = y + yy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && a[nx][ny] == 1 && vis[nx][ny] == 0)
                se(nx, ny, n, p, a);
        }
    }
    int cal(int a, int b, int n) {
        int x1 = a / n, y1 = a % n, x2 = b / n, y2 = b % n;
        return abs(x1 - x2) + abs(y1 - y2) - 1;
    }
};
int main()
{
	return 0;
}